package com.fanshuai.algorithms.greedy;

import com.fanshuai.algorithms.datastructure.graph.*;
import com.fanshuai.algorithms.datastructure.tree.binarytree.BoolValue;

import java.util.*;

/**
 * 最小生成树  设G=(V,E)是一个连通图，设G'是G的子集，如果G'是包含G所有顶点的一颗树，则G'称为G的一颗生成树。
 * 生成树所有边的权重和，生成生成树的cost, cost最小的生成树称为最小生成树
 *
 * prime算法：按顶点生成
 * kruskal算法：按边生成
 *
 * prime算法和kruskal算法均为贪心算法
 */
public class MinTree {

    /**
     * prime算法生成最小生成树
     * 设图G=(V, E),V表示顶点，E表示边。初始化顶点集合U, 选择任意一个顶点加入U
     *
     * （1）从U中选择任意顶点node, V-U中选择任意顶点node1，使得node和node1的距离最小
     * （2）将node1加入U，回到（1）重复操作，直到U=V
     *
     * @param matrix  图的邻接矩阵
     * @return  返回一颗树 用指向parent的树表示 数组下标表示顶点序号，数组元素表示父顶点序号
     */
    public static List<Edge> prime(int[][] matrix) {
        int n = matrix.length - 1; //顶点数量
        List<Edge> minTree = new ArrayList<>(); //生成树的边数量为n - 1

        Set<Integer> u = new HashSet<>(); //将顶点1放入u中
        u.add(1);
        Set<Integer> v = new HashSet<>();  //v中顶点为[2..n]
        for (int i = 2; i <= n; i++) {
            v.add(i);
        }

        while (!v.isEmpty()) {
            Edge edge = getMinEdge(matrix, u, v);
            minTree.add(edge);

            u.add(edge.dest);
            v.remove(edge.dest);
        }

        return minTree;
    }

    private static Edge getMinEdge(int[][] matrix, Set<Integer> u, Set<Integer> v) {
        int min = Integer.MAX_VALUE;
        int src = 0, dest = 0;

        for (int ui: u) {
            for (int vi : v) {
                if (matrix[ui][vi] < min) {
                    min = matrix[ui][vi];
                    src = ui;
                    dest = vi;
                }
            }
        }

        return new Edge(src, dest, min);
    }

    /**
     * kruskal算法  贪心算法
     * 设图G=(V,E)，初始化全部顶点集合S，S没有边相连
     * （1）每次取权值最小的边edge，如果edge在S中没有构成回路，则将edge加入S; 否则放弃这条边
     * （2）重复步骤1，直到已获取n-1条边，此时构成最小生成树
     * @param edges
     * @return
     */
    public static List<Edge> kruskal(List<Edge> edges, int n) {
        List<Edge> edges0 = new ArrayList<>(edges);
        edges0.sort(new Comparator<Edge>() {  //按权值排序
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        IndirectGraph2<Integer> minTree = new IndirectGraph2<>(n); //最小生成树
        int k = 0;
        while (k < n - 1) {
            Edge edge = findNextEdge(edges0, minTree); //获取未组成环的最小的边
            if (null == edge) {
                break;
            }
            minTree.addEdge(edge.src, edge.dest, edge.weight); //加入n-1条边
            edges0.remove(edge);

            k++;
        }

        return minTree.getAllEdges();
    }

    /**
     * 获取下一条边
     * @param edges
     * @param minTree
     * @return
     */
    private static Edge findNextEdge(List<Edge> edges, Graph2<Integer> minTree) {
        if (edges.size() == 0) {
            return null;
        }

        Edge edge = edges.get(0);
        while (isCycle(minTree, edge) && edges.size() > 0) {
            edges.remove(edge);  //构成环路，删除顶点
            edge = edges.get(0);
        }

        if (edges.size() == 0 && isCycle(minTree, edge)) {
            return null;
        } else {
            return edge;
        }
    }

    /**
     * 判断最小生成树加入边后，是否构成环
     * @param minTree
     * @param edge
     * @return
     */
    private static boolean isCycle(Graph2<Integer> minTree, Edge edge) {
        if (null == edge || minTree.getSize() == 0) {
            return false;
        }

        minTree.addEdge(edge.src, edge.dest, edge.weight);
        boolean cycle = isCycleGraph(minTree, edge.src);
        minTree.delEdge(edge.src, edge.dest);

        return cycle;
    }

    /**
     * 判断图是否构成循环
     * 方法1：通过BFS
     * 方法2：通过Union-Find
     * @param graph
     * @return
     */
    private static boolean isCycleGraph(Graph2<Integer> graph, int src) {
        int size = graph.getSize();
        if (size == 0) {
            return false;
        }

        BoolValue boolValue = new BoolValue(false);
        int[] visited = new int[size + 1];
        isCycleGraphBFS(graph, src, -1, visited, boolValue);

        return boolValue.value;
    }

    /**
     * 深度优先搜索
     *
     * 从src节点开始搜索，节点有3中状态，黑，白，灰
     * 初始节点为白色，访问节点后，节点变为灰色；
     * 访问当前灰色节点的所有邻接点，将邻接点变为灰色；
     * 所有邻接点访问完后，将当前灰色节点变为黑色
     *
     * 当访问的邻接点为灰色，且邻接点的邻接点不是上一次访问的节点时（上一个节点的邻接点可能并未遍历完，有可能是灰色），构成环
     *
     * 白--0  灰--1  黑--2
     * @param graph
     * @param src
     * @return
     */
    private static void isCycleGraphBFS(Graph2<Integer> graph, int src, int last, int[] visited, BoolValue
            boolValue) {
        if (visited[src] == 2) {
            return;
        }

        visited[src] = 1; //当前节点置灰

        List<Edge> edges = graph.getEdges(src);
        for (Edge edge : edges) {
            int dest = edge.dest;
            if (visited[dest] == 0) {
                isCycleGraphBFS(graph, dest, src, visited, boolValue); //深度优先遍历白色节点
            } else if (visited[dest] == 1 && dest != last) { //当邻接点为灰色，且不是上一个节点时，构成环
                boolValue.value = true;
                return;
            }
        }

        visited[src] = 2; //当前节点所有邻接点已遍历，置为黑色
    }

    /**
     * 并查集初始化
     * @param father
     */
    private static void init(int[] father) {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    /**
     * 并查集  获取集合的祖先
     * @param father
     * @param x
     */
    private static int findRoot(int[] father, int x) {
        int root = x;
        while (father[root] != root) {
            root = father[root];
        }

        while (father[x] != root) {
            int p = father[x];
            father[x] = root;
            x = p;
        }

        return root;
    }

    /**
     * 并查集  连接两个集合
     * @param u
     * @param v
     */
    private static void union(int[] father, int u, int v) {
        int uRoot = findRoot(father, u);
        int vRoot = findRoot(father, v);

        if (uRoot != vRoot) {
            father[uRoot] = father[vRoot] = Math.min(uRoot, vRoot);
        }
    }

    /**
     * 图是否构成一个环  并查集实现
     *
     * 使用图的边初始化并查集；
     * 遍历各条边，更新并查集；
     * 无向图： 在遍历u-v边时，如果u和v的父亲不相同，合并u-v；如果是一个父亲，说明构成环
     * 有向图：在遍历u-v边时，如果u不是v的父亲，设置u是v的父亲；如果u是v的父亲，构成环
     * @param graph
     */
    private static boolean isCycleUnionFind(Graph2<Integer> graph) {
        List<Edge> edges = graph.getAllEdges();
        boolean direct = graph.getDirect();
        int size = graph.getSize();

        if (direct) {
            return isCycleUnionFindDirect(edges, size);
        } else {
            return isCycleUnionFind(edges, size);
        }
    }

    //无向图判断是否为环
    private static boolean isCycleUnionFind(List<Edge> edges, int n) {
        int[] father = new int[n + 1];
        init(father); //初始化并查集

        for (Edge edge : edges) {
            int src = edge.src;
            int dest = edge.dest;
            if (findRoot(father, src) == findRoot(father, dest)) {
                return true;
            } else {
                union(father, src, dest);
            }
        }
        return false;
    }

    //有向图判断是否为环  此方法未调试成功
    private static boolean isCycleUnionFindDirect(List<Edge> edges, int n) {
        int[] father = new int[n + 1];
        init(father); //初始化并查集

        for (Edge edge : edges) {
            int src = edge.src;
            int dest = edge.dest;
            if (father[dest] == father[src]) {
                return true;
            } else {
                father[dest] = findRoot(father, src);
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] a1 = new int[][] {{1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {2, 5, 3}, {3, 4, 5},
                {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 6}};

        //IndirectGraph<Integer> graph = new IndirectGraph<>(6);
        IndirectGraph2<Integer> graph2 = new IndirectGraph2<>(6);

        for (int[] i : a1) {
            //graph.addEdge(i[0], i[1], i[2]);
            graph2.addEdge(i[0], i[1], i[2]);
        }

        //List<Edge> edges = prime(graph.getMatrix());
        List<Edge> edges2 = kruskal(graph2.getAllEdges(), 6);

        //System.out.println(edges);
        System.out.println(edges2);

        testCycle();
    }

    private static void testCycle() {
        int[][] a1 = new int[][] {{1, 2, 6}, {1, 3, 1}, {1, 4, 5}};
        int[][] a2 = new int[][] {{1, 2, 6}, {1, 3, 1}, {2, 3, 5}};
        int[][] a3 = new int[][] {{1, 2, 6}, {1, 4, 5}, {2, 3, 5}, {3, 4, 5}, {5, 6, 1}};
        int[][] a4 = new int[][] {{1, 2, 6}, {2, 3, 5}, {3, 1, 1}};

        testCycle(a1, 1);
        testCycle(a2, 2);
        testCycle(a3, 3);
        testCycle(a3, 1);
        testCycle(a3, 5);
        testCycle(a4, 1);
    }

    private static void testCycle(int[][] a, int src) {
        IndirectGraph2<Integer> graph2 = new IndirectGraph2<>(6);
        DirectGraph2<Integer> graph21 = new DirectGraph2<>(6);

        for (int[] i : a) {
            graph2.addEdge(i[0], i[1], i[2]);
            graph21.addEdge(i[0], i[1], i[2]);
        }

        boolean b = isCycleGraph(graph21, src);
        //boolean b = isCycleUnionFind(graph21);
        System.out.println(b);


    }
}
